import java.util.ArrayList;
import java.io.*;

public class DShortestPath {
	class Edge
	{
		int edge;
		int weight;
	}
	
	class Edge2{
		int tail;
		int head;
		int weight;
		
		public Edge2(){}
		
		public Edge2(Edge2 origin)
		{
			tail = origin.tail;
			head = origin.head;
			weight = origin.weight;
		}
	}

	ArrayList<ArrayList<Edge>> Vertices;
	
	int VerticesCount;
	
	public DShortestPath(int n)
	{
		VerticesCount = n;
		Vertices = new ArrayList<ArrayList<Edge>>(n);
	}
	
	
	public void ConvertStringVertices(String str)
	{
		String [] sArray = str.split("\t");
		
		ArrayList<Edge> edges = new ArrayList<Edge>();
		for(int i = 1; i < sArray.length; i++)
		{
			String [] sEdge = sArray[i].split(",");
			Edge edge = new Edge();
			edge.edge = Integer.parseInt(sEdge[0]) - 1;
			edge.weight = Integer.parseInt(sEdge[1]);
			edges.add(edge);
		}
		
		Vertices.add(edges);
	}
	
	
	public void InitVertices()
	{
		File file = new File("D:\\algorithm\\wk5\\dijkstraData.txt");
		BufferedReader reader = null;
		try{
			reader = new BufferedReader(new FileReader(file));
			String str = null;
			
			while((str = reader.readLine()) != null)
			{
				ConvertStringVertices(str);
			}
			reader.close();
		}catch (IOException e){
			e.printStackTrace();
		}finally{
			if(reader != null){
				try{
					reader.close();
				}catch (IOException e2){
					
				}
			}
		}
//		for(int i = 0; i < VerticesCount; i++)
//		{
//			ArrayList<Edge> edges = new ArrayList<Edge>(i+1);
//			for(int j = 0; j < i+1; j++)
//			{
//				Edge edge = new Edge();
//				edge.edge = j;
//				edge.weight = j;
//				edges.add(edge);
//			}
//			Vertices.add(edges);
//		}
	}
	
	public void PrintVertices()
	{
		for(int i = 0; i < Vertices.size(); i++)
		{
			System.out.print(i + 1 +"\t");
			ArrayList<Edge> edges = Vertices.get(i);
			for(int j = 0; j < edges.size(); j++)
			{
				Edge edge = edges.get(j);
				System.out.print(edge.edge + 1 +"," + edge.weight + "\t");				
			}
			System.out.print("\n");
		}
	}
	
	
	public void ComputeShortestPath()
	{
		InitVertices();
		//PrintVertices();
		RunDijkstra();
	}
	
	public Edge2 GetMinEdgeByIndex(int vertex)
	{		
		int weight = 1000000;
		int head = 0;
		
		ArrayList<Edge> temp = Vertices.get(vertex);
		for(int i = 0; i < temp.size(); i++)
		{
			Edge edge = temp.get(i);
			if(edge.weight < weight)
			{
				weight = edge.weight;
				head = edge.edge;
			}
		}
		
		if(weight < 1000000)
		{
			Edge2 minEdge = new Edge2();
			minEdge.tail = vertex;
			minEdge.head = head;
			minEdge.weight = weight;
			
			return minEdge;
		}
		
		return null;
	}
	
	
	public int GetMinEdge(ArrayList<Edge2> edges)
	{
		int weight = 100000;
		int index = -1;
		for(int i = 0; i < edges.size(); i++)
		{
			Edge2 e = edges.get(i);
			if(e.weight < weight)
			{
				weight = e.weight;
				index = i;
			}
		}
		
		return index;
	}
	
	
	public void RemoveEdgeByHead(int head)
	{
		for(int i = 0; i < Vertices.size(); i++)
		{
			ArrayList<Edge> edges = Vertices.get(i);
			for(int j = 0; j < edges.size(); j++)
			{
				Edge e = edges.get(j);
				
				if(e.edge == head)
				{
					edges.remove(j);
				}
			}
		}
	}
	
	public void CalculateMinEdges(ArrayList<Edge> ShortestPath, ArrayList<Edge2> MinEdges)
	{
		for(int i = 0; i < ShortestPath.size(); i++)
		{
			Edge e = ShortestPath.get(i);
			
			Edge2 e2 = GetMinEdgeByIndex(e.edge);
			
			if(e2 != null)
			{
				e2.weight += e.weight;
				Edge2 newE2 = new Edge2(e2);
				MinEdges.add(newE2);
			}
		}
	}
	
	public void RunDijkstra()
	{
		ArrayList<Edge> ShortestPath = new ArrayList<Edge>(200);
		Edge edge = new Edge();
		edge.edge = 0;
		edge.weight = 0;
		ShortestPath.add(edge);
		
		ArrayList<Edge2> MinEdges = new ArrayList<Edge2>();		
		
		RemoveEdgeByHead(0);
		Edge2 e2 = GetMinEdgeByIndex(0);
		Edge2 newE2 = new Edge2(e2);
		MinEdges.add(newE2);
		//int count = Vertices.size() - 1;
		
		while(MinEdges.size() > 0 )//&& count-- > 0)
		{
			int index = GetMinEdge(MinEdges);
			e2 = MinEdges.get(index);
			
			edge = new Edge();
			edge.edge = e2.head;
			edge.weight = e2.weight;
			//GetShortestPathByVertex(ShortestPath, e2.tail) + e2.weight; 
					//((Edge)ShortestPath.get(e2.tail)).weight;
			
			ShortestPath.add(edge);
			//MinEdges.remove(index);
			
			//delete all the edges which has vertex e2.head as its head
			RemoveEdgeByHead(e2.head);
			
			//compute new min edges
			MinEdges.clear();
			CalculateMinEdges(ShortestPath, MinEdges);			
		}
		
		PrintShortestPath(ShortestPath);
	}
	
	public int GetShortestPathByVertex(ArrayList<Edge> sp, int vertex)
	{
		for(int i = 0; i < sp.size(); i++)
		{
			Edge e = sp.get(i);
			if(e.edge == vertex)
			{
				return e.weight;
			}
		}
		
		return 1000000;
	}
	
	
	public void PrintShortestPath(ArrayList<Edge> sp)
	{
		for(int i = 0; i < sp.size(); i++)
		{			
			Edge e = sp.get(i);
			if(e.edge + 1 == 7 || e.edge + 1 == 37 || e.edge + 1 == 59 || e.edge + 1 == 82 || e.edge + 1 == 99 ||
					e.edge + 1 == 115 || e.edge + 1 == 133 || e.edge + 1 == 165 || e.edge + 1 == 188 || e.edge + 1 == 197)
			{
				System.out.print(e.edge + 1 + "\t" + e.weight + "\n");
			}
		}
	}
}
